import java.util.Arrays;
import java.util.PriorityQueue;

public class Sort {
    //直接插入排序
    //时间复杂度为O(N²)
    //在数据越有序的情况下，时间复杂度可以达到O(N)
    public void insertSort(int[] arr) {
        int length = arr.length;
        for (int i = 1; i < length; i++) {
            int tmp = arr[i];
            int j = i - 1;
            for (; j >= 0; j--) {
                if(arr[j] > tmp) {
                    arr[j + 1] = arr[j];
                } else {
                    arr[j + 1] = tmp;
                    break;
                }
            }
            arr[j + 1] = tmp;
        }
    }

    //希尔排序
    //时间复杂度为O(N^1.3 ~ N^1.5)
    public void shellSort(int[] arr) {
        int len = arr.length;
        int gap = len / 2;
        while(gap > 0) {
            shell(arr,gap);
            gap /= 2;
        }
    }

    private void shell(int[] arr, int gap) {
        int len = arr.length;
        for(int i = gap; i < len; i++) {
            int tmp = arr[i];
            int j = i - gap;
            for(; j >= 0; j -= gap) {
                if(arr[j] > tmp) {
                    arr[j+gap] = arr[j];
                } else {
                    arr[j+gap] = tmp;
                    break;
                }
            }
            arr[j+gap] = tmp;
        }
    }

    //简单选择排序
    //时间复杂度永远为O(N²)
    public void selectSort(int[] arr) {
        int len = arr.length;
        for (int i = 0; i < len - 1; i++) {
            int minIndex = i;
            for (int j = i+1; j < len; j++) {
                if(arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
            }
            swap(arr,i,minIndex);
        }
    }

    private void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

    //堆排序
    //时间复杂度为O(NlogN)
    public void heapSort(int[] arr) {
        //建大堆
        for (int parent = (arr.length - 1 - 1) / 2; parent >= 0; parent--) {
            shiftDown(arr,parent,arr.length);
        }

        //升序排序
        for (int i = arr.length - 1; i > 0; i--) {
            swap(arr,0,i);
            shiftDown(arr,0, i);
        }
    }

    public void shiftDown(int[] arr, int parent, int size) {
        int child = parent * 2 + 1;
        while(child < size) {
            if(child + 1 < size && arr[child+1] > arr[child]) {
                child++;
            }
            if(arr[parent] < arr[child]) {
                swap(arr,parent,child);
                parent = child;
                child = parent * 2 + 1;
            } else {
                break;
            }
        }
    }

    //冒泡排序
    public void bubbleSort(int[] arr) {
        int len = arr.length;
        boolean flag = true;
        for (int i = 0; flag && i < len - 1; i++) {
            flag = false;
            for (int j = 0; j < len - i - 1; j++) {
                if(arr[j] > arr[j+1]) {
                    flag = true;
                    swap(arr,j,j+1);
                }
            }
        }
    }

    //快速排序
    public void quickSort(int[] arr) {
        quick(arr,0,arr.length - 1);
    }

    private void quick(int[] arr, int left, int right) {
        while(left >= right) {
            return;
        }

        int pivot = partition(arr,left,right);

        quick(arr,left,pivot-1);
        quick(arr,pivot+1,right);
    }

    private int partition(int[] arr, int left, int right) {
        int key = arr[left];
        int tmpL = left;
        while(left < right) {
            while(left < right && arr[right] >= key) {
                right--;
            }
            while(left < right && arr[left] <= key) {
                left++;
            }
            swap(arr,left,right);
        }
        swap(arr,left,tmpL);

        return left;
    }

    //归并排序
    public void mergerSort(int[] arr) {
        merger(arr, 0, arr.length - 1);
    }

    private void merger(int[] arr, int left, int right) {
        while(left >= right) {
            return;
        }

        //分解
        int mid = (left + right) / 2;
        merger(arr,left,mid);
        merger(arr,mid+1,right);

        //合并
        merger_sort(arr,left,mid,right);
    }

    private void merger_sort(int[] arr, int left, int mid, int right) {
        int s1 = left;
        int e1 = mid;
        int s2 = mid + 1;
        int e2 = right;

        int[] tmp = new int[right - left + 1];
        int k = 0;
        while(s1 <= e1 && s2 <= e2) {
            if(arr[s1] < arr[s2]) {
                tmp[k++] = arr[s1++];
            } else {
                tmp[k++] = arr[s2++];
            }
        }

        while(s1 <= e1) {
            tmp[k++] = arr[s1++];
        }

        while(s2 <= e2) {
            tmp[k++] = arr[s2++];
        }

        for(int i = 0; i < k; i++) {
            arr[left+i] = tmp[i];
        }
    }

    public static void main(String[] args) {
        int[] arr = {1,5,3,45,10,32,0,24};
        Sort sort = new Sort();
        //sort.insertSort(arr);
        //sort.shellSort(arr);
        //sort.selectSort(arr);
        //sort.heapSort(arr);
        //sort.bubbleSort(arr);
        //sort.quickSort(arr);
        sort.mergerSort(arr);
        System.out.println(Arrays.toString(arr));
        //PriorityQueue<Integer> queue = new PriorityQueue<>();
    }
}
